class Solution {
public:
    string addBinary(string a, string b) {
        size_t sa = a.size(), sb = b.size();
        if(a.size() < b.size()){  // a为较长
            swap(a, b);  
            swap(sa, sb);
        } 
        string res;
        int carry = 0;   // 进位标记
        // 逆序处理相加
        int i = sa-1;
        for(int j = sb-1; i >= 0 && j >= 0; --i, --j){
            int temp = (a[i]-'0') + (b[j]-'0') + carry;
            res += (temp%2)+'0';
            carry = (temp >= 2); 
        }
        while(i >= 0){
            int temp = a[i--]-'0' + carry;
            res += (temp%2)+'0';
            carry = (temp >= 2);  // 大于等于2结果为1、否则为0
        }
        // 最高位是否需要进位
        if(carry == 1) res.push_back('1');
        reverse(res.begin(), res.end());
        return res;
    }
};